{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "def createC1(dataSet):\n",
    "    C1 = []\n",
    "    for transaction in dataSet:\n",
    "        for item in transaction:\n",
    "            if not [item] in C1:\n",
    "                C1.append([item])\n",
    "\n",
    "    C1.sort()\n",
    "    return list(map(frozenset, C1))  # use frozen set so we\n",
    "    # can use it as a key in a dict\n",
    "\n",
    "\n",
    "def scanD(D, Ck, minSupport):\n",
    "    \"\"\"\n",
    "    由Ck生成Lk\n",
    "    :param D: 交易记录，每条交易记录用一个集合表示\n",
    "    :param Ck:\n",
    "    :param minSupport:\n",
    "    :return: retList, supportData. 前者是Lk，后者是一个字典，key为频繁项，v为该频繁项的支持度\n",
    "    \"\"\"\n",
    "    ssCnt = {}\n",
    "    for tid in D:  # 对每一条交易记录tid\n",
    "        for can in Ck:  # 对Ck里的每个频繁项\n",
    "            if can.issubset(tid):  # 如果can是tid的子集，说明频繁项can出现了一次\n",
    "                if can not in ssCnt:  # 如果can不是字典ssCnt的键，则创建这个键\n",
    "                    ssCnt[can] = 1\n",
    "                else:\n",
    "                    ssCnt[can] += 1  # 如果can已经在ssCnt中，则将其加1\n",
    "    numItems = float(len(D))\n",
    "    retList = []\n",
    "    supportData = {}\n",
    "    for key in ssCnt:  # key是frozenset([])，是一个频繁项\n",
    "        support = ssCnt[key] / numItems\n",
    "        if support >= minSupport:\n",
    "            retList.insert(0, key)\n",
    "        supportData[key] = support\n",
    "    return retList, supportData\n",
    "\n",
    "\n",
    "def aprioriGen(Lk, k):\n",
    "    \"\"\"\n",
    "    由L_(k-1)生成Ck\n",
    "    :param Lk: 其实是L_(k-1)\n",
    "    :param k: Ck的k\n",
    "    :return: Ck\n",
    "    \"\"\"\n",
    "    retList = []\n",
    "    lenLk = len(Lk)\n",
    "    for i in range(lenLk):\n",
    "        for j in range(i + 1, lenLk):\n",
    "            L1 = list(Lk[i])[:k - 2]  # 只对前k-2项相同的集合取\"并\"操作，防止产生重复的集合\n",
    "            L2 = list(Lk[j])[:k - 2]\n",
    "            L1.sort()\n",
    "            L2.sort()\n",
    "            if L1 == L2:  # if first k-2 elements are equal\n",
    "                retList.append(Lk[i] | Lk[j])  # set union\n",
    "    return retList\n",
    "\n",
    "\n",
    "def apriori(dataSet, minSupport=0.5):\n",
    "    C1 = createC1(dataSet)\n",
    "    D = list(map(set, dataSet))\n",
    "    L1, supportData = scanD(D, C1, minSupport)\n",
    "    L = [L1]\n",
    "    k = 2\n",
    "    while len(L[k - 2]) > 0:  # 当找到的Lk为空时，结束循环\n",
    "        Ck = aprioriGen(L[k - 2], k)\n",
    "        Lk, supK = scanD(D, Ck, minSupport)  # scan DB to get Lk\n",
    "        supportData.update(supK)  # 合并支持度字典\n",
    "        L.append(Lk)\n",
    "        k += 1\n",
    "    return L, supportData"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "raw_data = pd.read_csv(\"Groceries.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>ID</th>\n",
       "      <th>items</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>{citrus fruit,semi-finished bread,margarine,re...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>{tropical fruit,yogurt,coffee}</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>{whole milk}</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>{pip fruit,yogurt,cream cheese ,meat spreads}</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>{other vegetables,whole milk,condensed milk,lo...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   ID                                              items\n",
       "0   1  {citrus fruit,semi-finished bread,margarine,re...\n",
       "1   2                     {tropical fruit,yogurt,coffee}\n",
       "2   3                                       {whole milk}\n",
       "3   4      {pip fruit,yogurt,cream cheese ,meat spreads}\n",
       "4   5  {other vegetables,whole milk,condensed milk,lo..."
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "raw_data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9835, 2)"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "raw_data.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "item_list = raw_data['items'].to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "item_list = [x[1:-1] for x in item_list]\n",
    "# [\"xx, yy, zz\", \"aa,bb,cc\", \"dd,ee\", ... ,]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "item_list = [x.split(',') for x in item_list]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['citrus fruit', 'semi-finished bread', 'margarine', 'ready soups'],\n",
       " ['tropical fruit', 'yogurt', 'coffee'],\n",
       " ['whole milk'],\n",
       " ['pip fruit', 'yogurt', 'cream cheese ', 'meat spreads'],\n",
       " ['other vegetables',\n",
       "  'whole milk',\n",
       "  'condensed milk',\n",
       "  'long life bakery product']]"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_list[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "169"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kind = set()\n",
    "for i in item_list:\n",
    "    for j in i:\n",
    "        kind.add(j)\n",
    "len(kind)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**共169种商品种类**  \n",
    "kind是所有商品种类的集合，例如{\"salty snack\", \"baby food\", \"cake bar\", ...}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "kind_dict_1 = dict(zip([x for x in range(len(kind))], kind))  # 键是数字，值是商品\n",
    "kind_dict_2 = dict(zip(kind, [x for x in range(len(kind))]))  # 键是商品，值是数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- kind_dict_1:  \n",
    "{0: 'salty snack',\n",
    " 1: 'baby food',\n",
    " 2: 'cake bar',\n",
    " 3: 'sausage',\n",
    " 4: 'bags',\n",
    " ...} \n",
    "- kind_dict_2:  \n",
    "和kind_dict_1相反，键是商品，值是数字"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "item_index_list = item_list.copy()\n",
    "for i in item_index_list:\n",
    "    # item_list: [['citrus fruit', 'semi-finished bread', 'margarine', 'ready soups'],\n",
    "    # ['tropical fruit', 'yogurt', 'coffee'],\n",
    "    # ['whole milk'],...]\n",
    "    for j in range(len(i)):\n",
    "        i[j] = kind_dict_2[i[j]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- item_index_list格式  \n",
    "[[43, 76, 162, 50],\n",
    " [49, 157, 119],\n",
    " [67],\n",
    " [55, 157, 121, 77],...]  \n",
    " 最外层列表的每一项是一个列表，代表一条交易记录"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "L, support_data = apriori(item_index_list, 0.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在0.01支持度下，有L1、L2、L3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generateRules(L, supportData, minConf=0.7):  # supportData is a dict coming from scanD\n",
    "    bigRuleList = []\n",
    "    for i in range(1, len(L)):  # only get the sets with two or more items\n",
    "        for freqSet in L[i]:\n",
    "            H1 = [frozenset([item]) for item in freqSet]\n",
    "            if (i > 1):\n",
    "                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)\n",
    "            else:\n",
    "                calcConf(freqSet, H1, supportData, bigRuleList, minConf)\n",
    "    return bigRuleList\n",
    "\n",
    "\n",
    "def calcConf(freqSet, H, supportData, brl, minConf=0.7):\n",
    "    prunedH = []  # create new list to return\n",
    "    for conseq in H:\n",
    "        conf = supportData[freqSet] / supportData[freqSet - conseq]  # calc confidence\n",
    "        if conf >= minConf:\n",
    "            print(freqSet - conseq, '-->', conseq, 'conf:', conf)\n",
    "            brl.append((freqSet - conseq, conseq, conf))\n",
    "            prunedH.append(conseq)\n",
    "    return prunedH\n",
    "\n",
    "\n",
    "def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):\n",
    "    m = len(H[0])\n",
    "    if (len(freqSet) > (m + 1)):  # try further merging\n",
    "        Hmp1 = aprioriGen(H, m + 1)  # create Hm+1 new candidates\n",
    "        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)\n",
    "        if (len(Hmp1) > 1):  # need at least two sets to merge\n",
    "            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "frozenset({164}) --> frozenset({67}) conf: 0.4099526066350711\n",
      "frozenset({85}) --> frozenset({7}) conf: 0.45901639344262296\n",
      "frozenset({11}) --> frozenset({67}) conf: 0.4398340248962655\n",
      "frozenset({25}) --> frozenset({67}) conf: 0.4057971014492754\n",
      "frozenset({153}) --> frozenset({67}) conf: 0.4107883817427386\n",
      "frozenset({121}) --> frozenset({67}) conf: 0.41538461538461546\n",
      "frozenset({98}) --> frozenset({67}) conf: 0.4434250764525994\n",
      "frozenset({164}) --> frozenset({7}) conf: 0.4170616113744075\n",
      "frozenset({51}) --> frozenset({67}) conf: 0.41454545454545455\n",
      "frozenset({114}) --> frozenset({67}) conf: 0.40217391304347827\n",
      "frozenset({162}) --> frozenset({67}) conf: 0.4131944444444444\n",
      "frozenset({31}) --> frozenset({67}) conf: 0.4050387596899225\n",
      "frozenset({137}) --> frozenset({67}) conf: 0.4249471458773784\n",
      "frozenset({46}) --> frozenset({67}) conf: 0.44140625\n",
      "frozenset({82}) --> frozenset({67}) conf: 0.47275641025641024\n",
      "frozenset({110}) --> frozenset({67}) conf: 0.449645390070922\n",
      "frozenset({110}) --> frozenset({7}) conf: 0.40283687943262414\n",
      "frozenset({111}) --> frozenset({67}) conf: 0.4444444444444445\n",
      "frozenset({48}) --> frozenset({67}) conf: 0.44869402985074625\n",
      "frozenset({98}) --> frozenset({7}) conf: 0.41590214067278286\n",
      "frozenset({48}) --> frozenset({7}) conf: 0.43470149253731344\n",
      "frozenset({49}) --> frozenset({67}) conf: 0.40310077519379844\n",
      "frozenset({15}) --> frozenset({67}) conf: 0.4904580152671756\n",
      "frozenset({157}) --> frozenset({67}) conf: 0.40160349854227406\n",
      "frozenset({28}) --> frozenset({67}) conf: 0.4972477064220184\n"
     ]
    }
   ],
   "source": [
    "rules = generateRules(L, support_data, 0.4)  # 最小置信度取0.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
